//************************************************************
//    > File Name: merge-intervals.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月28日 13:59:39
//***********************************************************
//lintcode #156

#include<bits/stdc++.h>
using namespace std;
struct Interval{
	int start,end;
	Interval(int start,int end){
		this->start=start;
		this->end=end;
	}
};
bool cmp(const Interval &a,const Interval &b){
	return a.start<b.start;
}

vector<Interval> merge(vector<Interval> &intervals){
	if(intervals.empty()) return intervals;

	sort(intervals.begin(),intervals.end(),cmp);
	vector<Interval> result={intervals[0]};
	for(int i=1;i<intervals.size();++i){
		Interval& tmp = result.back();
		if(intervals[i].start<=tmp.end){
			tmp.end=max(tmp.end,intervals[i].end);
		}else{
			result.push_back(intervals[i]);
		}
	}
	return result;
}
int main(){
	vector<Interval> a={
		{1,3},{2,6},{7,8}
	};

	vector<Interval> b=merge(a);
	for(int i=0;i<b.size();++i){
		cout<<b[i].start<<" "<<b[i].end<<endl;
	}
}
